package com.xxx.springboot.pojo.bean.tireNode;

public class TrieNode {

    // 存储当前节点的子节点
    private final TrieNode[] children;
    // 标记该节点是否是一个单词的结束
    private boolean isEndOfWord;

    public TrieNode() {
        // 初始化子节点数组，通常为26个字母
        children = new TrieNode[26];
        isEndOfWord = false;
    }

    // 添加一个单词到Trie树中
    public void insert(String word) {
        TrieNode current = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // 从Trie树删除一个单词
    public boolean delete(String word) {
        return delete(this, word, 0);
    }

    private boolean delete(TrieNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord) {
                return false; // 单词不存在于树中
            }
            current.isEndOfWord = false;
            return canDelete(current); // 返回是否可以删除该节点
        }

        char ch = word.charAt(index);
        int childIndex = ch - 'a';
        TrieNode child = current.children[childIndex];

        if (child == null) {
            return false; // 单词不存在于树中
        }

        boolean canDeleteChild = delete(child, word, index + 1);

        if (canDeleteChild) {
            current.children[childIndex] = null;
            return canDelete(current);
        }

        return false;
    }

    // 判断节点是否能被删除
    private boolean canDelete(TrieNode node) {
        if(node.isEndOfWord){
            return false;
        }
        for (TrieNode child : node.children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }

    // 检查一个单词是否存在于Trie树中
    public boolean search(String word) {
        TrieNode current = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current.isEndOfWord;
    }

    // 检查是否有以给定前缀开头的单词存在
    public boolean startsWith(String prefix) {
        TrieNode current = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return true;
    }

}
